/* 

给定一个二叉树，检查它是否是镜像对称的。

 

例如，二叉树 [1,2,2,3,4,4,3] 是对称的。

    1
   / \
  2   2
 / \ / \
3  4 4  3
 

但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:

    1
   / \
  2   2
   \   \
   3    3
 

进阶：

你可以运用递归和迭代两种方法解决这个问题吗？

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/symmetric-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

*/

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */

// 递归
var isSymmetric = function (root) {
    const helper = (node1, node2) => {
        // 都为空
        if (!node1 && !node2) return true;
        // 一个为空一个不为空，或者两个节点值不相等
        if (!node1 || !node2 || node1.val !== node2.val) return false;
        return helper(node1.left, node2.right) && helper(node1.right, node2.left);
    }
    if (root === null) return true;
    return helper(root.left, root.right);
};

// 迭代
var isSymmetric = function (root) {
    if (root === null) return true;
    const queue = [root.left, root.right];
    let node1, node2;
    while (queue.length) {
        node1 = queue.shift();
        node2 = queue.shift();
        // 两节点均为空
        if (!node1 && !node2) continue;
        // 一个为空一个不为空，或者两个节点值不相等
        if (!node1 || !node2 || node1.val !== node2.val) return false;
        queue.push(node1.left);
        queue.push(node2.right);
        queue.push(node1.right);
        queue.push(node2.left);
    }
    return true;
};